#include<bits/stdc++.h>
using namespace std;

//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) 
//	{
//        unordered_map<int, int> hash;
//        for (int i = 0; i < nums.size(); i++)
//        {
//			int tmp = target - nums[i];
//        	if (hash.count(tmp)) 
//        	{
////        		cout << hash[tmp] << ' ' << i;
//        		return {hash[tmp], i};
//			}
//			hash[nums[i]] = i;
//		}
//		return {-1, -1};
//    }
//};

//class Solution {
//public:
//    bool CheckPermutation(string s1, string s2) {
//    	if (s1.size() != s2.size())
//		{
//			return false;
//		}
//        unordered_map<char, int> hash;
//        // 初始化哈希表
//        for (int i = 0; i < s1.size(); i++)
//        {
//			hash[s1[i]] = 0;
//		}
//		// 计数
//		for (int i = 0; i < s1.size(); i++)
//        {
//			++hash[s1[i]];
//		}
//		
//		for (int i = 0; i < s2.size(); i++)
//        {
//        	// 没找到
//			if (hash.count(s2[i]) == 0)
//			{
//				return false;	
//			}  
//			--hash[s2[i]];
//			if (hash[s2[i]] < 0)
//			{
//				return false;
//			}
//		}
//		return true;
//    }
//};

//class Solution {
//public:
//    bool CheckPermutation(std::string s1, std::string s2) {
//        // 长度不相等
//        if (s1.size() != s2.size()) {
//            return false;
//        }
//        std::unordered_map<char, int> hash;
//        // 统计 s1 中字符的出现次数
//        for (int i = 0; i < s1.size(); i++) {
//            ++hash[s1[i]];
//        }
//        // 检查 s2 中字符的出现次数
//        for (int i = 0; i < s2.size(); i++) {
//            --hash[s2[i]];
//            // 对应字符数量不相等
//            if (hash[s2[i]] < 0) {
//                return false;
//            }
//        }
//        return true;
//    }
//};

//class Solution {
//public:
//    bool containsDuplicate(vector<int>& nums) {
//        unordered_map<int, int> hash;
//        for (int i = 0; i < nums.size(); i++)
//        {
//        	if (hash.count(nums[i]))
//        	{
//        		return true;
//			}
//			hash[nums[i]] = 0;
//		}
//		return false;
//    }
//};

//class Solution {
//public:
//    bool containsNearbyDuplicate(vector<int>& nums, int k) {
//        unordered_map<int, int> hash;
//        for (int i = 0; i < nums.size(); i++)
//        {
//        	if (hash.count(nums[i]) && (abs(hash[nums[i]] - i) <= k))
//        	{
//        		return true;
//			}
//            hash[nums[i]] = i;
//		}
//		return false;
//    }
//};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        vector<vector<string>> ret;
        string tmp;
        for (int i = 0; i < strs.size(); i++)
        {
            tmp = strs[i];
            sort(tmp.begin(), tmp.end());
            if (hash.count(tmp) == 0)
            {
                vector<string> vs;
                vs.push_back(strs[i]);
                hash[tmp] = vs;
            }
            else
            {
                hash[tmp].push_back(strs[i]);
            }
        }
        for (auto& [key, value] : hash)
        {
			ret.push_back(value);
        }
        return ret;
    }
};

int main()
{
//	vector<int> v = {3, 3};
	vector<string> strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
	Solution().groupAnagrams(strs);

	return 0;
}